home *** CD-ROM | disk | FTP | other *** search
/ Aminet 32 / Aminet 32 (1999)(Schatztruhe)[!][Aug 1999].iso / Aminet / dev / lang / Python151_Src.lha / Python1.5_Source / Objects / listobject.c < prev    next >
C/C++ Source or Header  |  1998-05-30  |  23KB  |  1,107 lines
  1. /***********************************************************
  2. Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
  3. The Netherlands.
  4.  
  5.                         All Rights Reserved
  6.  
  7. Permission to use, copy, modify, and distribute this software and its
  8. documentation for any purpose and without fee is hereby granted,
  9. provided that the above copyright notice appear in all copies and that
  10. both that copyright notice and this permission notice appear in
  11. supporting documentation, and that the names of Stichting Mathematisch
  12. Centrum or CWI or Corporation for National Research Initiatives or
  13. CNRI not be used in advertising or publicity pertaining to
  14. distribution of the software without specific, written prior
  15. permission.
  16.  
  17. While CWI is the initial source for this software, a modified version
  18. is made available by the Corporation for National Research Initiatives
  19. (CNRI) at the Internet address ftp://ftp.python.org.
  20.  
  21. STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
  22. REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
  23. MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
  24. CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  25. DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  26. PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  27. TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  28. PERFORMANCE OF THIS SOFTWARE.
  29.  
  30. ******************************************************************/
  31.  
  32. /* List object implementation */
  33.  
  34. #include "Python.h"
  35.  
  36. #ifdef STDC_HEADERS
  37. #include <stddef.h>
  38. #else
  39. #include <sys/types.h>        /* For size_t */
  40. #endif
  41.  
  42. #include "protos/listobject_protos.h"
  43.  
  44. #define ROUNDUP(n, PyTryBlock) \
  45.     ((((n)+(PyTryBlock)-1)/(PyTryBlock))*(PyTryBlock))
  46.  
  47. static int
  48. roundupsize(n)
  49.     int n;
  50. {
  51.     if (n < 500)
  52.         return ROUNDUP(n, 10);
  53.     else
  54.         return ROUNDUP(n, 100);
  55. }
  56.  
  57. #define NRESIZE(var, type, nitems) PyMem_RESIZE(var, type, roundupsize(nitems))
  58.  
  59. PyObject *
  60. PyList_New(size)
  61.     int size;
  62. {
  63.     int i;
  64.     PyListObject *op;
  65.     size_t nbytes;
  66.     if (size < 0) {
  67.         PyErr_BadInternalCall();
  68.         return NULL;
  69.     }
  70.     nbytes = size * sizeof(PyObject *);
  71.     /* Check for overflow */
  72.     if (nbytes / sizeof(PyObject *) != (size_t)size) {
  73.         return PyErr_NoMemory();
  74.     }
  75.     op = (PyListObject *) malloc(sizeof(PyListObject));
  76.     if (op == NULL) {
  77.         return PyErr_NoMemory();
  78.     }
  79.     if (size <= 0) {
  80.         op->ob_item = NULL;
  81.     }
  82.     else {
  83.         op->ob_item = (PyObject **) malloc(nbytes);
  84.         if (op->ob_item == NULL) {
  85.             free((ANY *)op);
  86.             return PyErr_NoMemory();
  87.         }
  88.     }
  89.     op->ob_type = &PyList_Type;
  90.     op->ob_size = size;
  91.     for (i = 0; i < size; i++)
  92.         op->ob_item[i] = NULL;
  93.     _Py_NewReference(op);
  94.     return (PyObject *) op;
  95. }
  96.  
  97. int
  98. PyList_Size(op)
  99.     PyObject *op;
  100. {
  101.     if (!PyList_Check(op)) {
  102.         PyErr_BadInternalCall();
  103.         return -1;
  104.     }
  105.     else
  106.         return ((PyListObject *)op) -> ob_size;
  107. }
  108.  
  109. static PyObject *indexerr;
  110.  
  111. PyObject *
  112. PyList_GetItem(op, i)
  113.     PyObject *op;
  114.     int i;
  115. {
  116.     if (!PyList_Check(op)) {
  117.         PyErr_BadInternalCall();
  118.         return NULL;
  119.     }
  120.     if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
  121.         if (indexerr == NULL)
  122.             indexerr = PyString_FromString(
  123.                 "list index out of range");
  124.         PyErr_SetObject(PyExc_IndexError, indexerr);
  125.         return NULL;
  126.     }
  127.     return ((PyListObject *)op) -> ob_item[i];
  128. }
  129.  
  130. int
  131. PyList_SetItem(op, i, newitem)
  132.     register PyObject *op;
  133.     register int i;
  134.     register PyObject *newitem;
  135. {
  136.     register PyObject *olditem;
  137.     register PyObject **p;
  138.     if (!PyList_Check(op)) {
  139.         Py_XDECREF(newitem);
  140.         PyErr_BadInternalCall();
  141.         return -1;
  142.     }
  143.     if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
  144.         Py_XDECREF(newitem);
  145.         PyErr_SetString(PyExc_IndexError,
  146.                 "list assignment index out of range");
  147.         return -1;
  148.     }
  149.     p = ((PyListObject *)op) -> ob_item + i;
  150.     olditem = *p;
  151.     *p = newitem;
  152.     Py_XDECREF(olditem);
  153.     return 0;
  154. }
  155.  
  156. static int
  157. ins1(self, where, v)
  158.     PyListObject *self;
  159.     int where;
  160.     PyObject *v;
  161. {
  162.     int i;
  163.     PyObject **items;
  164.     if (v == NULL) {
  165.         PyErr_BadInternalCall();
  166.         return -1;
  167.     }
  168.     items = self->ob_item;
  169.     NRESIZE(items, PyObject *, self->ob_size+1);
  170.     if (items == NULL) {
  171.         PyErr_NoMemory();
  172.         return -1;
  173.     }
  174.     if (where < 0)
  175.         where = 0;
  176.     if (where > self->ob_size)
  177.         where = self->ob_size;
  178.     for (i = self->ob_size; --i >= where; )
  179.         items[i+1] = items[i];
  180.     Py_INCREF(v);
  181.     items[where] = v;
  182.     self->ob_item = items;
  183.     self->ob_size++;
  184.     return 0;
  185. }
  186.  
  187. int
  188. PyList_Insert(op, where, newitem)
  189.     PyObject *op;
  190.     int where;
  191.     PyObject *newitem;
  192. {
  193.     if (!PyList_Check(op)) {
  194.         PyErr_BadInternalCall();
  195.         return -1;
  196.     }
  197.     return ins1((PyListObject *)op, where, newitem);
  198. }
  199.  
  200. int
  201. PyList_Append(op, newitem)
  202.     PyObject *op;
  203.     PyObject *newitem;
  204. {
  205.     if (!PyList_Check(op)) {
  206.         PyErr_BadInternalCall();
  207.         return -1;
  208.     }
  209.     return ins1((PyListObject *)op,
  210.         (int) ((PyListObject *)op)->ob_size, newitem);
  211. }
  212.  
  213. /* Methods */
  214.  
  215. static void
  216. list_dealloc(op)
  217.     PyListObject *op;
  218. {
  219.     int i;
  220.     if (op->ob_item != NULL) {
  221.         for (i = 0; i < op->ob_size; i++) {
  222.             Py_XDECREF(op->ob_item[i]);
  223.         }
  224.         free((ANY *)op->ob_item);
  225.     }
  226.     free((ANY *)op);
  227. }
  228.  
  229. static int
  230. list_print(op, fp, flags)
  231.     PyListObject *op;
  232.     FILE *fp;
  233.     int flags;
  234. {
  235.     int i;
  236.  
  237.     i = Py_ReprEnter((PyObject*)op);
  238.     if (i != 0) {
  239.         if (i < 0)
  240.             return i;
  241.         fprintf(fp, "[...]");
  242.         return 0;
  243.     }
  244.     fprintf(fp, "[");
  245.     for (i = 0; i < op->ob_size; i++) {
  246.         if (i > 0)
  247.             fprintf(fp, ", ");
  248.         if (PyObject_Print(op->ob_item[i], fp, 0) != 0) {
  249.             Py_ReprLeave((PyObject *)op);
  250.             return -1;
  251.         }
  252.     }
  253.     fprintf(fp, "]");
  254.     Py_ReprLeave((PyObject *)op);
  255.     return 0;
  256. }
  257.  
  258. static PyObject *
  259. list_repr(v)
  260.     PyListObject *v;
  261. {
  262.     PyObject *s, *comma;
  263.     int i;
  264.  
  265.     i = Py_ReprEnter((PyObject*)v);
  266.     if (i != 0) {
  267.         if (i > 0)
  268.             return PyString_FromString("[...]");
  269.         return NULL;
  270.     }
  271.     s = PyString_FromString("[");
  272.     comma = PyString_FromString(", ");
  273.     for (i = 0; i < v->ob_size && s != NULL; i++) {
  274.         if (i > 0)
  275.             PyString_Concat(&s, comma);
  276.         PyString_ConcatAndDel(&s, PyObject_Repr(v->ob_item[i]));
  277.     }
  278.     Py_XDECREF(comma);
  279.     PyString_ConcatAndDel(&s, PyString_FromString("]"));
  280.     Py_ReprLeave((PyObject *)v);
  281.     return s;
  282. }
  283.  
  284. static int
  285. list_compare(v, w)
  286.     PyListObject *v, *w;
  287. {
  288.     int len = (v->ob_size < w->ob_size) ? v->ob_size : w->ob_size;
  289.     int i;
  290.     for (i = 0; i < len; i++) {
  291.         int cmp = PyObject_Compare(v->ob_item[i], w->ob_item[i]);
  292.         if (cmp != 0)
  293.             return cmp;
  294.     }
  295.     return v->ob_size - w->ob_size;
  296. }
  297.  
  298. static int
  299. list_length(a)
  300.     PyListObject *a;
  301. {
  302.     return a->ob_size;
  303. }
  304.  
  305. static PyObject *
  306. list_item(a, i)
  307.     PyListObject *a;
  308.     int i;
  309. {
  310.     if (i < 0 || i >= a->ob_size) {
  311.         if (indexerr == NULL)
  312.             indexerr = PyString_FromString(
  313.                 "list index out of range");
  314.         PyErr_SetObject(PyExc_IndexError, indexerr);
  315.         return NULL;
  316.     }
  317.     Py_INCREF(a->ob_item[i]);
  318.     return a->ob_item[i];
  319. }
  320.  
  321. static PyObject *
  322. list_slice(a, ilow, ihigh)
  323.     PyListObject *a;
  324.     int ilow, ihigh;
  325. {
  326.     PyListObject *np;
  327.     int i;
  328.     if (ilow < 0)
  329.         ilow = 0;
  330.     else if (ilow > a->ob_size)
  331.         ilow = a->ob_size;
  332.     if (ihigh < 0)
  333.         ihigh = 0;
  334.     if (ihigh < ilow)
  335.         ihigh = ilow;
  336.     else if (ihigh > a->ob_size)
  337.         ihigh = a->ob_size;
  338.     np = (PyListObject *) PyList_New(ihigh - ilow);
  339.     if (np == NULL)
  340.         return NULL;
  341.     for (i = ilow; i < ihigh; i++) {
  342.         PyObject *v = a->ob_item[i];
  343.         Py_INCREF(v);
  344.         np->ob_item[i - ilow] = v;
  345.     }
  346.     return (PyObject *)np;
  347. }
  348.  
  349. PyObject *
  350. PyList_GetSlice(a, ilow, ihigh)
  351.     PyObject *a;
  352.     int ilow, ihigh;
  353. {
  354.     if (!PyList_Check(a)) {
  355.         PyErr_BadInternalCall();
  356.         return NULL;
  357.     }
  358.     return list_slice((PyListObject *)a, ilow, ihigh);
  359. }
  360.  
  361. static PyObject *
  362. list_concat(a, bb)
  363.     PyListObject *a;
  364.     PyObject *bb;
  365. {
  366.     int size;
  367.     int i;
  368.     PyListObject *np;
  369.     if (!PyList_Check(bb)) {
  370.         PyErr_BadArgument();
  371.         return NULL;
  372.     }
  373. #define b ((PyListObject *)bb)
  374.     size = a->ob_size + b->ob_size;
  375.     np = (PyListObject *) PyList_New(size);
  376.     if (np == NULL) {
  377.         return NULL;
  378.     }
  379.     for (i = 0; i < a->ob_size; i++) {
  380.         PyObject *v = a->ob_item[i];
  381.         Py_INCREF(v);
  382.         np->ob_item[i] = v;
  383.     }
  384.     for (i = 0; i < b->ob_size; i++) {
  385.         PyObject *v = b->ob_item[i];
  386.         Py_INCREF(v);
  387.         np->ob_item[i + a->ob_size] = v;
  388.     }
  389.     return (PyObject *)np;
  390. #undef b
  391. }
  392.  
  393. static PyObject *
  394. list_repeat(a, n)
  395.     PyListObject *a;
  396.     int n;
  397. {
  398.     int i, j;
  399.     int size;
  400.     PyListObject *np;
  401.     PyObject **p;
  402.     if (n < 0)
  403.         n = 0;
  404.     size = a->ob_size * n;
  405.     np = (PyListObject *) PyList_New(size);
  406.     if (np == NULL)
  407.         return NULL;
  408.     p = np->ob_item;
  409.     for (i = 0; i < n; i++) {
  410.         for (j = 0; j < a->ob_size; j++) {
  411.             *p = a->ob_item[j];
  412.             Py_INCREF(*p);
  413.             p++;
  414.         }
  415.     }
  416.     return (PyObject *) np;
  417. }
  418.  
  419. static int
  420. list_ass_slice(a, ilow, ihigh, v)
  421.     PyListObject *a;
  422.     int ilow, ihigh;
  423.     PyObject *v;
  424. {
  425.     /* Because [X]DECREF can recursively invoke list operations on
  426.        this list, we must postpone all [X]DECREF activity until
  427.        after the list is back in its canonical shape.  Therefore
  428.        we must allocate an additional array, 'recycle', into which
  429.        we temporarily copy the items that are deleted from the
  430.        list. :-( */
  431.     PyObject **recycle, **p;
  432.     PyObject **item;
  433.     int n; /* Size of replacement list */
  434.     int d; /* Change in size */
  435.     int k; /* Loop index */
  436. #define b ((PyListObject *)v)
  437.     if (v == NULL)
  438.         n = 0;
  439.     else if (PyList_Check(v)) {
  440.         n = b->ob_size;
  441.         if (a == b) {
  442.             /* Special case "a[i:j] = a" -- copy b first */
  443.             int ret;
  444.             v = list_slice(b, 0, n);
  445.             ret = list_ass_slice(a, ilow, ihigh, v);
  446.             Py_DECREF(v);
  447.             return ret;
  448.         }
  449.     }
  450.     else {
  451.         PyErr_BadArgument();
  452.         return -1;
  453.     }
  454.     if (ilow < 0)
  455.         ilow = 0;
  456.     else if (ilow > a->ob_size)
  457.         ilow = a->ob_size;
  458.     if (ihigh < 0)
  459.         ihigh = 0;
  460.     if (ihigh < ilow)
  461.         ihigh = ilow;
  462.     else if (ihigh > a->ob_size)
  463.         ihigh = a->ob_size;
  464.     item = a->ob_item;
  465.     d = n - (ihigh-ilow);
  466.     if (ihigh > ilow)
  467.         p = recycle = PyMem_NEW(PyObject *, (ihigh-ilow));
  468.     else
  469.         p = recycle = NULL;
  470.     if (d <= 0) { /* Delete -d items; recycle ihigh-ilow items */
  471.         for (k = ilow; k < ihigh; k++)
  472.             *p++ = item[k];
  473.         if (d < 0) {
  474.             for (/*k = ihigh*/; k < a->ob_size; k++)
  475.                 item[k+d] = item[k];
  476.             a->ob_size += d;
  477.             NRESIZE(item, PyObject *, a->ob_size); /* Can't fail */
  478.             a->ob_item = item;
  479.         }
  480.     }
  481.     else { /* Insert d items; recycle ihigh-ilow items */
  482.         NRESIZE(item, PyObject *, a->ob_size + d);
  483.         if (item == NULL) {
  484.             PyMem_XDEL(recycle);
  485.             PyErr_NoMemory();
  486.             return -1;
  487.         }
  488.         for (k = a->ob_size; --k >= ihigh; )
  489.             item[k+d] = item[k];
  490.         for (/*k = ihigh-1*/; k >= ilow; --k)
  491.             *p++ = item[k];
  492.         a->ob_item = item;
  493.         a->ob_size += d;
  494.     }
  495.     for (k = 0; k < n; k++, ilow++) {
  496.         PyObject *w = b->ob_item[k];
  497.         Py_XINCREF(w);
  498.         item[ilow] = w;
  499.     }
  500.     if (recycle) {
  501.         while (--p >= recycle)
  502.             Py_XDECREF(*p);
  503.         PyMem_DEL(recycle);
  504.     }
  505.     return 0;
  506. #undef b
  507. }
  508.  
  509. int
  510. PyList_SetSlice(a, ilow, ihigh, v)
  511.     PyObject *a;
  512.     int ilow, ihigh;
  513.     PyObject *v;
  514. {
  515.     if (!PyList_Check(a)) {
  516.         PyErr_BadInternalCall();
  517.         return -1;
  518.     }
  519.     return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
  520. }
  521.  
  522. static int
  523. list_ass_item(a, i, v)
  524.     PyListObject *a;
  525.     int i;
  526.     PyObject *v;
  527. {
  528.     PyObject *old_value;
  529.     if (i < 0 || i >= a->ob_size) {
  530.         PyErr_SetString(PyExc_IndexError,
  531.                 "list assignment index out of range");
  532.         return -1;
  533.     }
  534.     if (v == NULL)
  535.         return list_ass_slice(a, i, i+1, v);
  536.     Py_INCREF(v);
  537.     old_value = a->ob_item[i];
  538.     a->ob_item[i] = v;
  539.     Py_DECREF(old_value); 
  540.     return 0;
  541. }
  542.  
  543. static PyObject *
  544. ins(self, where, v)
  545.     PyListObject *self;
  546.     int where;
  547.     PyObject *v;
  548. {
  549.     if (ins1(self, where, v) != 0)
  550.         return NULL;
  551.     Py_INCREF(Py_None);
  552.     return Py_None;
  553. }
  554.  
  555. static PyObject *
  556. listinsert(self, args)
  557.     PyListObject *self;
  558.     PyObject *args;
  559. {
  560.     int i;
  561.     PyObject *v;
  562.     if (!PyArg_Parse(args, "(iO)", &i, &v))
  563.         return NULL;
  564.     return ins(self, i, v);
  565. }
  566.  
  567. static PyObject *
  568. listappend(self, args)
  569.     PyListObject *self;
  570.     PyObject *args;
  571. {
  572.     PyObject *v;
  573.     if (!PyArg_Parse(args, "O", &v))
  574.         return NULL;
  575.     return ins(self, (int) self->ob_size, v);
  576. }
  577.  
  578. #define NEWSORT
  579.  
  580. #ifdef NEWSORT
  581.  
  582. /* New quicksort implementation for arrays of object pointers.
  583.    Thanks to discussions with Tim Peters. */
  584.  
  585. /* CMPERROR is returned by our comparison function when an error
  586.    occurred.  This is the largest negative integer (0x80000000 on a
  587.    32-bit system). */
  588. #define CMPERROR ( (int) ((unsigned int)1 << (8*sizeof(int) - 1)) )
  589.  
  590. /* Comparison function.  Takes care of calling a user-supplied
  591.    comparison function (any callable Python object).  Calls the
  592.    standard comparison function, cmpobject(), if the user-supplied
  593.    function is NULL. */
  594.  
  595. static int
  596. docompare(x, y, compare)
  597.     PyObject *x;
  598.     PyObject *y;
  599.     PyObject *compare;
  600. {
  601.     PyObject *args, *res;
  602.     int i;
  603.  
  604.     if (compare == NULL) {
  605.         i = PyObject_Compare(x, y);
  606.         if (i && PyErr_Occurred())
  607.             i = CMPERROR;
  608.         return i;
  609.     }
  610.  
  611.     args = Py_BuildValue("(OO)", x, y);
  612.     if (args == NULL)
  613.         return CMPERROR;
  614.     res = PyEval_CallObject(compare, args);
  615.     Py_DECREF(args);
  616.     if (res == NULL)
  617.         return CMPERROR;
  618.     if (!PyInt_Check(res)) {
  619.         Py_DECREF(res);
  620.         PyErr_SetString(PyExc_TypeError,
  621.                 "comparison function should return int");
  622.         return CMPERROR;
  623.     }
  624.     i = PyInt_AsLong(res);
  625.     Py_DECREF(res);
  626.     if (i < 0)
  627.         return -1;
  628.     if (i > 0)
  629.         return 1;
  630.     return 0;
  631. }
  632.  
  633. /* Straight insertion sort.  More efficient for sorting small arrays. */
  634.  
  635. static int
  636. insertionsort(array, size, compare)
  637.     PyObject **array;    /* Start of array to sort */
  638.     int size;    /* Number of elements to sort */
  639.     PyObject *compare;/* Comparison function object, or NULL for default */
  640. {
  641.     register PyObject **a = array;
  642.     register PyObject **end = array+size;
  643.     register PyObject **p;
  644.  
  645.     for (p = a+1; p < end; p++) {
  646.         register PyObject *key = *p;
  647.         register PyObject **q = p;
  648.         while (--q >= a) {
  649.             register int k = docompare(*q, key, compare);
  650.             if (k == CMPERROR)
  651.                 return -1;
  652.             if (k <= 0)
  653.                 break;
  654.             *(q+1) = *q;
  655.             *q = key; /* For consistency */
  656.         }
  657.     }
  658.  
  659.     return 0;
  660. }
  661.  
  662. /* MINSIZE is the smallest array we care to partition; smaller arrays
  663.    are sorted using a straight insertion sort (above).  It must be at
  664.    least 2 for the quicksort implementation to work.  Assuming that
  665.    comparisons are more expensive than everything else (and this is a
  666.    good assumption for Python), it should be 10, which is the cutoff
  667.    point: quicksort requires more comparisons than insertion sort for
  668.    smaller arrays. */
  669. #define MINSIZE 10
  670.  
  671. /* STACKSIZE is the size of our work stack.  A rough estimate is that
  672.    this allows us to sort arrays of MINSIZE * 2**STACKSIZE, or large
  673.    enough.  (Because of the way we push the biggest partition first,
  674.    the worst case occurs when all subarrays are always partitioned
  675.    exactly in two.) */
  676. #define STACKSIZE 64
  677.  
  678. /* Quicksort algorithm.  Return -1 if an exception occurred; in this
  679.    case we leave the array partly sorted but otherwise in good health
  680.    (i.e. no items have been removed or duplicated). */
  681.  
  682. static int
  683. quicksort(array, size, compare)
  684.     PyObject **array;    /* Start of array to sort */
  685.     int size;    /* Number of elements to sort */
  686.     PyObject *compare;/* Comparison function object, or NULL for default */
  687. {
  688.     register PyObject *tmp, *pivot;
  689.     register PyObject **lo, **hi, **l, **r;
  690.     int top, k, n, n2;
  691.     PyObject **lostack[STACKSIZE];
  692.     PyObject **histack[STACKSIZE];
  693.  
  694.     /* Start out with the whole array on the work stack */
  695.     lostack[0] = array;
  696.     histack[0] = array+size;
  697.     top = 1;
  698.  
  699.     /* Repeat until the work stack is empty */
  700.     while (--top >= 0) {
  701.         lo = lostack[top];
  702.         hi = histack[top];
  703.  
  704.         /* If it's a small one, use straight insertion sort */
  705.         n = hi - lo;
  706.         if (n < MINSIZE) {
  707.             /* 
  708.                  * skip it.  The insertion sort at the end will 
  709.              * catch these 
  710.              */
  711.             continue;
  712.         }
  713.  
  714.         /* Choose median of first, middle and last item as pivot */
  715.         
  716.         l = lo + (n>>1); /* Middle */
  717.         r = hi - 1;    /* Last */
  718.  
  719.         k = docompare(*l, *lo, compare);
  720.         if (k == CMPERROR)
  721.             return -1;
  722.         if (k < 0)
  723.             { tmp = *lo; *lo = *l; *l = tmp; }
  724.  
  725.         k = docompare(*r, *l, compare);
  726.         if (k == CMPERROR)
  727.             return -1;
  728.         if (k < 0)
  729.             { tmp = *r; *r = *l; *l = tmp; }
  730.  
  731.         k = docompare(*l, *lo, compare);
  732.         if (k == CMPERROR)
  733.             return -1;
  734.         if (k < 0)
  735.             { tmp = *l; *l = *lo; *lo = tmp; }
  736.         pivot = *l;
  737.  
  738.         /* Partition the array */
  739.         l = lo+1;
  740.         r = hi-2;
  741.         for (;;) {
  742.             /* Move left index to element > pivot */
  743.             while (l < hi) {
  744.                 k = docompare(*l, pivot, compare); 
  745.                 if (k == CMPERROR)
  746.                     return -1;
  747.                 if (k >= 0)
  748.                     break;
  749.                 l++;
  750.             }
  751.             /* Move right index to element < pivot */
  752.             while (r >= lo) {
  753.                 k = docompare(pivot, *r, compare);
  754.                 if (k == CMPERROR)
  755.                     return -1;
  756.                 if (k >= 0)
  757.                     break;
  758.                 r--;
  759.             }
  760.  
  761.             /* If they met, we're through */
  762.             if (l < r) {
  763.                 /* Swap elements and continue */
  764.                 tmp = *l; *l = *r; *r = tmp; 
  765.                 l++; r--;
  766.             }
  767.             else if (l == r) {
  768.                 l++; r--;
  769.                 break;
  770.             }
  771.  
  772.             if (l > r)
  773.                 break;
  774.         }
  775.  
  776.  
  777.         /* We have now reached the following conditions:
  778.             lo <= r < l <= hi
  779.             all x in [lo,r) are <= pivot
  780.             all x in [r,l)  are == pivot
  781.             all x in [l,hi) are >= pivot
  782.            The partitions are [lo,r) and [l,hi)
  783.          */
  784.  
  785.         /* Push biggest partition first */
  786.         n = r - lo;
  787.         n2 = hi - l;
  788.         if (n > n2) {
  789.             /* First one is bigger */
  790.             if (n > MINSIZE) {
  791.                 lostack[top] = lo;
  792.                 histack[top++] = r;
  793.                 if (n2 > MINSIZE) {
  794.                     lostack[top] = l;
  795.                     histack[top++] = hi;
  796.                 }
  797.             }
  798.         } else {
  799.             /* Second one is bigger */
  800.             if (n2 > MINSIZE) {
  801.                 lostack[top] = l;
  802.                 histack[top++] = hi;
  803.                 if (n > MINSIZE) {
  804.                     lostack[top] = lo;
  805.                     histack[top++] = r;
  806.                 }
  807.             }
  808.         }
  809.  
  810.         /* Should assert top < STACKSIZE-1 */
  811.     }
  812.  
  813.     /*
  814.      * Ouch - even if I screwed up the quicksort above, the
  815.      * insertionsort below will cover up the problem - just a
  816.      * performance hit would be noticable.   
  817.      */
  818.  
  819.     /* insertionsort is pretty fast on the partially sorted list */
  820.  
  821.     if (insertionsort(array, size, compare) < 0)
  822.         return -1;
  823.     
  824.     /* Succes */
  825.     return 0;
  826. }
  827.  
  828. static PyObject *
  829. listsort(self, compare)
  830.     PyListObject *self;
  831.     PyObject *compare;
  832. {
  833.     /* XXX Don't you *dare* changing the list's length in compare()! */
  834.     if (quicksort(self->ob_item, self->ob_size, compare) < 0)
  835.         return NULL;
  836.     Py_INCREF(Py_None);
  837.     return Py_None;
  838. }
  839.  
  840. #else /* !NEWSORT */
  841.  
  842. static PyObject *comparefunc;
  843.  
  844. static int
  845. cmp(v, w)
  846.     const ANY *v, *w;
  847. {
  848.     PyObject *t, *res;
  849.     long i;
  850.  
  851.     if (PyErr_Occurred())
  852.         return 0;
  853.  
  854.     if (comparefunc == NULL)
  855.         return PyObject_Compare(* (PyObject **) v, * (PyObject **) w);
  856.  
  857.     /* Call the user-supplied comparison function */
  858.     t = Py_BuildValue("(OO)", * (PyObject **) v, * (PyObject **) w);
  859.     if (t == NULL)
  860.         return 0;
  861.     res = PyEval_CallObject(comparefunc, t);
  862.     Py_DECREF(t);
  863.     if (res == NULL)
  864.         return 0;
  865.     if (!PyInt_Check(res)) {
  866.         PyErr_SetString(PyExc_TypeError,
  867.                 "comparison function should return int");
  868.         i = 0;
  869.     }
  870.     else {
  871.         i = PyInt_AsLong(res);
  872.         if (i < 0)
  873.             i = -1;
  874.         else if (i > 0)
  875.             i = 1;
  876.     }
  877.     Py_DECREF(res);
  878.     return (int) i;
  879. }
  880.  
  881. static PyObject *
  882. listsort(self, args)
  883.     PyListObject *self;
  884.     PyObject *args;
  885. {
  886.     PyObject *save_comparefunc;
  887.     if (self->ob_size <= 1) {
  888.         Py_INCREF(Py_None);
  889.         return Py_None;
  890.     }
  891.     save_comparefunc = comparefunc;
  892.     comparefunc = args;
  893.     if (comparefunc != NULL) {
  894.         /* Test the comparison function for obvious errors */
  895.         (void) cmp((ANY *)&self->ob_item[0], (ANY *)&self->ob_item[1]);
  896.         if (PyErr_Occurred()) {
  897.             comparefunc = save_comparefunc;
  898.             return NULL;
  899.         }
  900.     }
  901.     qsort((char *)self->ob_item,
  902.                 (int) self->ob_size, sizeof(PyObject *), cmp);
  903.     comparefunc = save_comparefunc;
  904.     if (PyErr_Occurred())
  905.         return NULL;
  906.     Py_INCREF(Py_None);
  907.     return Py_None;
  908. }
  909.  
  910. #endif
  911.  
  912. static PyObject *
  913. listreverse(self, args)
  914.     PyListObject *self;
  915.     PyObject *args;
  916. {
  917.     register PyObject **p, **q;
  918.     register PyObject *tmp;
  919.     
  920.     if (args != NULL) {
  921.         PyErr_BadArgument();
  922.         return NULL;
  923.     }
  924.  
  925.     if (self->ob_size > 1) {
  926.         for (p = self->ob_item, q = self->ob_item + self->ob_size - 1;
  927.                         p < q; p++, q--) {
  928.             tmp = *p;
  929.             *p = *q;
  930.             *q = tmp;
  931.         }
  932.     }
  933.     
  934.     Py_INCREF(Py_None);
  935.     return Py_None;
  936. }
  937.  
  938. int
  939. PyList_Reverse(v)
  940.     PyObject *v;
  941. {
  942.     if (v == NULL || !PyList_Check(v)) {
  943.         PyErr_BadInternalCall();
  944.         return -1;
  945.     }
  946.     v = listreverse((PyListObject *)v, (PyObject *)NULL);
  947.     if (v == NULL)
  948.         return -1;
  949.     Py_DECREF(v);
  950.     return 0;
  951. }
  952.  
  953. int
  954. PyList_Sort(v)
  955.     PyObject *v;
  956. {
  957.     if (v == NULL || !PyList_Check(v)) {
  958.         PyErr_BadInternalCall();
  959.         return -1;
  960.     }
  961.     v = listsort((PyListObject *)v, (PyObject *)NULL);
  962.     if (v == NULL)
  963.         return -1;
  964.     Py_DECREF(v);
  965.     return 0;
  966. }
  967.  
  968. PyObject *
  969. PyList_AsTuple(v)
  970.     PyObject *v;
  971. {
  972.     PyObject *w;
  973.     PyObject **p;
  974.     int n;
  975.     if (v == NULL || !PyList_Check(v)) {
  976.         PyErr_BadInternalCall();
  977.         return NULL;
  978.     }
  979.     n = ((PyListObject *)v)->ob_size;
  980.     w = PyTuple_New(n);
  981.     if (w == NULL)
  982.         return NULL;
  983.     p = ((PyTupleObject *)w)->ob_item;
  984.     memcpy((ANY *)p,
  985.            (ANY *)((PyListObject *)v)->ob_item,
  986.            n*sizeof(PyObject *));
  987.     while (--n >= 0) {
  988.         Py_INCREF(*p);
  989.         p++;
  990.     }
  991.     return w;
  992. }
  993.  
  994. static PyObject *
  995. listindex(self, args)
  996.     PyListObject *self;
  997.     PyObject *args;
  998. {
  999.     int i;
  1000.     
  1001.     if (args == NULL) {
  1002.         PyErr_BadArgument();
  1003.         return NULL;
  1004.     }
  1005.     for (i = 0; i < self->ob_size; i++) {
  1006.         if (PyObject_Compare(self->ob_item[i], args) == 0)
  1007.             return PyInt_FromLong((long)i);
  1008.         if (PyErr_Occurred())
  1009.             return NULL;
  1010.     }
  1011.     PyErr_SetString(PyExc_ValueError, "list.index(x): x not in list");
  1012.     return NULL;
  1013. }
  1014.  
  1015. static PyObject *
  1016. listcount(self, args)
  1017.     PyListObject *self;
  1018.     PyObject *args;
  1019. {
  1020.     int count = 0;
  1021.     int i;
  1022.     
  1023.     if (args == NULL) {
  1024.         PyErr_BadArgument();
  1025.         return NULL;
  1026.     }
  1027.     for (i = 0; i < self->ob_size; i++) {
  1028.         if (PyObject_Compare(self->ob_item[i], args) == 0)
  1029.             count++;
  1030.         if (PyErr_Occurred())
  1031.             return NULL;
  1032.     }
  1033.     return PyInt_FromLong((long)count);
  1034. }
  1035.  
  1036. static PyObject *
  1037. listremove(self, args)
  1038.     PyListObject *self;
  1039.     PyObject *args;
  1040. {
  1041.     int i;
  1042.     
  1043.     if (args == NULL) {
  1044.         PyErr_BadArgument();
  1045.         return NULL;
  1046.     }
  1047.     for (i = 0; i < self->ob_size; i++) {
  1048.         if (PyObject_Compare(self->ob_item[i], args) == 0) {
  1049.             if (list_ass_slice(self, i, i+1,
  1050.                        (PyObject *)NULL) != 0)
  1051.                 return NULL;
  1052.             Py_INCREF(Py_None);
  1053.             return Py_None;
  1054.         }
  1055.         if (PyErr_Occurred())
  1056.             return NULL;
  1057.     }
  1058.     PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
  1059.     return NULL;
  1060. }
  1061.  
  1062. static PyMethodDef list_methods[] = {
  1063.     {"append",    (PyCFunction)listappend},
  1064.     {"insert",    (PyCFunction)listinsert},
  1065.     {"remove",    (PyCFunction)listremove},
  1066.     {"index",    (PyCFunction)listindex},
  1067.     {"count",    (PyCFunction)listcount},
  1068.     {"reverse",    (PyCFunction)listreverse},
  1069.     {"sort",    (PyCFunction)listsort, 0},
  1070.     {NULL,        NULL}        /* sentinel */
  1071. };
  1072.  
  1073. static PyObject *
  1074. list_getattr(f, name)
  1075.     PyListObject *f;
  1076.     char *name;
  1077. {
  1078.     return Py_FindMethod(list_methods, (PyObject *)f, name);
  1079. }
  1080.  
  1081. static PySequenceMethods list_as_sequence = {
  1082.     (inquiry)list_length, /*sq_length*/
  1083.     (binaryfunc)list_concat, /*sq_concat*/
  1084.     (intargfunc)list_repeat, /*sq_repeat*/
  1085.     (intargfunc)list_item, /*sq_item*/
  1086.     (intintargfunc)list_slice, /*sq_slice*/
  1087.     (intobjargproc)list_ass_item, /*sq_ass_item*/
  1088.     (intintobjargproc)list_ass_slice, /*sq_ass_slice*/
  1089. };
  1090.  
  1091. PyTypeObject PyList_Type = {
  1092.     PyObject_HEAD_INIT(&PyType_Type)
  1093.     0,
  1094.     "list",
  1095.     sizeof(PyListObject),
  1096.     0,
  1097.     (destructor)list_dealloc, /*tp_dealloc*/
  1098.     (printfunc)list_print, /*tp_print*/
  1099.     (getattrfunc)list_getattr, /*tp_getattr*/
  1100.     0,        /*tp_setattr*/
  1101.     (cmpfunc)list_compare, /*tp_compare*/
  1102.     (reprfunc)list_repr, /*tp_repr*/
  1103.     0,        /*tp_as_number*/
  1104.     &list_as_sequence,    /*tp_as_sequence*/
  1105.     0,        /*tp_as_mapping*/
  1106. };
  1107.